// @algorithm @lc id=94 lang=cpp 
// @title binary-tree-inorder-traversal


// @test([1,null,2,3])=[1,3,2]
// @test([])=[]
// @test([1])=[1]
// @test([1,2])=[2,1]
// @test([1,null,2])=[1,2]
class Solution {
public:
    static void Recursion(TreeNode* root, vector<int> &res){ // 递归:T(n),M(n)
        if(!root) return;
        if(root->left) Recursion(root->left, res);
        res.push_back(root->val);
        if(root->right) Recursion(root->right, res);
    }
    static void Iteration(TreeNode* cur, vector<int> &res){ // 迭代(栈):T(n),M(n)
        list<TreeNode*> stk;
        while(cur || stk.size()){
            while(cur){ // iterate cur to find most left
                stk.push_back(cur);
                cur = cur->left;
            }
            cur = stk.back();
            res.push_back(cur->val); // visit *root [of most left]
            cur = cur->right; // iterate right
            stk.pop_back();
        }
    }
    static void Morris(TreeNode* cur, vector<int> &res){ // 莫里斯遍历:T(n),M(1)
        TreeNode * pre = NULL;
        while(cur){
            if(!cur->left){ // 无左孩子: visit(*cur), then iterate right
                res.push_back(cur->val);
                cur = cur->right;
            }else{ // 有左孩子:
                pre = cur->left;
                while(pre->right && pre->right!=cur)
                    pre = pre->right; // 查找 左子树的most_right
                if(NULL == pre->right){
                    pre->right = cur; // 使 [左子树的most_right]->right 指向 cur
                    cur = cur->left;  // iterate left
                }else{ // cur->left->right 指向 cur: cur->left是 [左子树的most_right], 左子树访问结束
                    res.push_back(cur->val);
                    cur = cur->right;
                    pre->right = NULL;
                }
            }
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        // Recursion(root, res);
        // Iteration(root, res);
        Morris(root, res);
        // print(res, "\n")
        return res;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */